package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * leet-code(22) 括号生成 递归
 *
 * @author Ringo
 * @date 2021/9/2 17:25
 */
public class GenerateParenthesis {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
        System.out.println(generateParenthesis(1));
    }

    public static List<String> generateParenthesis(int n) {
        if (n <= 0) return null;
        StringBuilder tempBuilder = new StringBuilder();
        List<String> ans = new ArrayList<>();
        generate(n, 0, 0, ans, tempBuilder);
        return ans;
    }

    public static void generate(int n, int open, int close, List<String> ans, StringBuilder tempBuilder) {
        // 左、右括号都等于 n 递归结束
        if (open == n && close == n) {
            ans.add(tempBuilder.toString());
            return;
        }

        // 左、右括号数量相等的时候, 只能添加左括号
        if (open == close) {
            tempBuilder.append("(");
            generate(n, open + 1, close, ans, tempBuilder);
            tempBuilder.deleteCharAt(tempBuilder.length() - 1);
        } else if (open > close) {
            // 左括号数量 > 右括号数量时, 可以加左括号, 也可以加右括号
            // 如果左括号数量 < n, 就加左括号
            if (open < n) {
                tempBuilder.append("(");
                generate(n, open + 1, close, ans, tempBuilder);
                tempBuilder.deleteCharAt(tempBuilder.length() - 1);
            }
            // 左括号数量满了, 才加右括号
            tempBuilder.append(")");
            generate(n, open, close + 1, ans, tempBuilder);
            tempBuilder.deleteCharAt(tempBuilder.length() - 1);
        }
    }
}
